package com.monkeyboy.binarysearch;

/**
 * 题目：
 * 数字在排序数组中出现的次数
 * <p>
 * Input:
 * nums = 1, 2, 3, 3, 3, 3, 4, 6
 * K = 3
 * <p>
 * Output:
 * 4
 * <p>
 * 解题思路：
 * 就是先通过二分查找快速定位到这个元素，然后再从这个元素下标的左边和右边依次循环
 *
 * @Author Gavin
 * @date 2021.04.08 10:05
 */
public class search02 {
    public static int solution(int[] nums, int k) {
        if (nums.length <= 0 || k < nums[0] || k > nums[nums.length-1]) {
            return 0;
        }
        int count = 0;
        int fond = -1;
        int low = 0;
        int high = nums.length - 1;
        int mid = -1;
        while (low < high) {
            mid = (low + high) / 2;
            if (nums[mid] == k) {
                count++;
                fond = mid;
                break;
            } else if (nums[mid] < k) {
                low = mid +1;
            } else {
                high = mid - 1;
            }
        }
        int pre = mid - 1;
        int after = mid + 1;
        while (pre > 0) {
            if (nums[pre] == k) {
                count++;
                pre--;
            } else {
                break;
            }
        }
        while (after < nums.length) {
            if (nums[after] == k) {
                count++;
                after++;
            } else {
                break;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 3, 3, 4, 5, 6};
        System.out.println(solution(nums, 6));
    }
}
